package com.kaifamiao.month03.day0319;

public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {8, 4, 5, 7, 1, 3, 6};//直接复制数组
        quickSort(arr, 0, arr.length - 1);
        print(arr);
    }

    private static int get_mid(int[] arr, int left, int right) {
        // 自定义排序中心轴，这里把 arr[left] 存到 temp 中去，此时 arr[left] 为空。 temp 相当于一个中间量
        int temp = arr[left];
        while (left < right) {
            // 当 left 与 right 指针相遇的时候退出循环，双指针遍历结束
            /*
             * right 指针从右往左遍历，当 arr[right] >= temp ，即满足以 temp 为中轴，小放左 ,大放右的条件时
             * right 指针继续往右遍历。当 arr[right] < temp 的时候，把当前值 arr[right] 赋给空置 arr[left]
             * 此时 arr[right] 成了空值。
             */
            while (arr[right] >= temp && left < right)
                right--;
            arr[left] = arr[right];
            while (arr[left] <= temp && left < right)
            /*
             * 到left指针从左往右遍历，当 arr[left] <= temp
             * ，即满足以temp为中轴，小放左，大放右的条件时，left指针继续往左遍历。
             * 当arr[left]>temp，把当前值 arr[left] 赋给空置 arr[right]
             * 此时arr[left]成了空值。
             */
                left++;
            arr[right] = arr[left];
        }
        // 经历了上面的循环实现了 temp 为中轴，小放左，大放右的格局
        arr[left] = temp;  // 最后把存放在 temp 值放回数组空arr[left]中
        return left;  // 返回中轴所在的下标位置。
    }

    private static void quickSort(int[] arr, int left, int right) {
        if (left < right) {
            /*将arr[left..right]均分为两部分arr[left..mid]和arr[mid+1..right]
             * ,以 temp 为中轴，小放左，大放右。这是第一步。*/
            int mid = get_mid(arr, left, right);//接收中轴所在的下标位置。
            quickSort(arr, left, mid - 1);//递归地对arr[left..mid]进行快速排序，使得左子序列有序
            quickSort(arr, mid + 1, right);//递归地对arr[mid+1..right]进行快速排序，使得左子序列有序
        }
    }

    public static void print(int[] arr) {
        for (int i : arr) {
            System.out.print(i + " ");
        }
    }
}
